package gss;

import org.apache.commons.math.fraction.BigFraction;
import static org.apache.commons.math.fraction.BigFraction.ONE;
import static org.apache.commons.math.fraction.BigFraction.ONE_HALF;
import static org.apache.commons.math.fraction.BigFraction.ZERO;

import static gss.BigFractionUtils.max;
import static gss.BigFractionUtils.min;

import java.util.Vector;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import static java.util.Collections.singleton;

/**
 * Represents a 2D line segment with arbitrary precision endpoints.
 * All segments must have non-zero length. In other words, the endpoints
 * must be distinct.
 * Also contains a {@code String} name which can be used for printing
 * and sorting and various other purposes. LineSegment is an immutable
 * class. 
 * @author mdm32
 */
public class LineSegment {
    private static final String ZEROLENGTH = 
	"Attempt to create zero-length segment";

    private BigFraction X1;
    private BigFraction Y1;
    private BigFraction X2;
    private BigFraction Y2;

    private BigFraction _dx;
    private BigFraction _dy;

    private static RadianComparator _radianComparator = 
	new RadianComparator();

    /**
     * Default constructor that creates a segment from (0,0) to (1,1) 
     * with a name of "0".
     */
    public LineSegment() {
        X1 = new BigFraction(0);
        Y1 = new BigFraction(0);
        X2 = new BigFraction(1);
        Y2 = new BigFraction(1);
	initializeDXY();
    }

    /**
     * Class constructor that creates a segment from the 4
     * coordinates given (x<sub>1</sub>, y<sub>1</sub>,
     * x<sub>2</sub>, y<sub>2</sub>).
     *
     * @param	x1	    x coordinate of first endpoint
     * @param	y1	    y coordinate of first endpoint
     * @param	x2	    x coordinate of second endpoint
     * @param	y2	    y coordinate of second endpoint
     */
    public LineSegment(BigFraction x1, BigFraction y1,
				    BigFraction x2, BigFraction y2 )
    {
	if (x2.equals(x1) && y2.equals(y1)) {
	    throw new RuntimeException(ZEROLENGTH + ": " +
		    x1 + " " + y1 + " " + x2 + " " + y2);
	}
        X1 = x1;
        Y1 = y1;
        X2 = x2;
        Y2 = y2;
	initializeDXY();
    }

    /**
     * Class constructor that creates a segment from the 4
     * coordinates given (x<sub>1</sub>, y<sub>1</sub>,
     * x<sub>2</sub>, y<sub>2</sub>).
     *
     * @param	x1	    x coordinate of first endpoint
     * @param	y1	    y coordinate of first endpoint
     * @param	x2	    x coordinate of second endpoint
     * @param	y2	    y coordinate of second endpoint
     */
    public LineSegment(double x1, double y1,
            double x2, double y2) {
        X1 = new BigFraction(x1);
        Y1 = new BigFraction(y1);
        X2 = new BigFraction(x2);
        Y2 = new BigFraction(y2);
	if (X2.equals(X1) && Y2.equals(Y1)) {
	    throw new RuntimeException(ZEROLENGTH + ": " +
		    X1 + " " + Y1 + " " + X2 + " " + Y2);
	}
	initializeDXY();
    }

    /**
     * Class constructor that creates a segment from the 2 endpoints
     * given.
     *
     * @param	a	    the first endpoint
     * @param	b	    the second endpoint
     */
    public LineSegment(Vertex a, Vertex b) {
        X1 = a.getX();
        Y1 = a.getY();
        X2 = b.getX();
        Y2 = b.getY();
	if (X2.equals(X1) && Y2.equals(Y1)) {
	    throw new RuntimeException(ZEROLENGTH + ": " +
		    X1 + " " + Y1 + " " + X2 + " " + Y2);
	}
	initializeDXY();
    }

    /**
     * @return	the x coordinate of the first endpoint
     */
    public BigFraction getX1() {
        return X1;
    }

    /**
     * @return	the x coordinate of the second endpoint
     */
    public BigFraction getX2() {
        return X2;
    }

    /**
     * @return	the y coordinate of the first endpoint
     */
    public BigFraction getY1() {
        return Y1;
    }

    /**
     * @return	the y coordinate of the second endpoint
     */
    public BigFraction getY2() {
        return Y2;
    }

    /**
     * @return	the first endpoint, with visibility 
     */
    public Vertex getVertex1() {
        return new Vertex(this, X1, Y1);
    }

    /**
     * @return	the second endpoint, with visibility 
     */
    public Vertex getVertex2() {
        return new Vertex(this, X2, Y2);
    }

    /**
     * @return	X<sub>2</sub> - X<sub>1</sub>
     */
    public BigFraction dx() {
	return _dx;
    }

    /**
     * @return	Y<sub>2</sub> - Y<sub>1</sub>
     */
    public BigFraction dy() {
	return _dy;
    }

    private final void initializeDXY() {
	_dx = X2.subtract(X1);
	_dy = Y2.subtract(Y1);
    }

    /**
     * Computes the length of this segment.
     * @return	the double precision length of this segment
     */
    public double segmentLength() {
        BigFraction cy = dx();
        BigFraction cx = dx();
        return Math.sqrt(
		((cx.multiply(cx)).add(cy.multiply(cy))).doubleValue());
    }

    /**
     * Returns a string representation of this segment.
     * @return	a String in the format: "name (X1,Y1), (X2,Y2)"
     */
    @Override
    public String toString() {
        return ("(" + X1 + "," + Y1 +
                "), (" + X2 + "," + Y2 + ")");
    }

    /**
     * Tests if this segment is vertical.
     * @return	false if this segment is vertical
     */
    public boolean isNotVertical() {
        if (X1.equals(X2)) { return false; }
	// else
        return true;
    }

    /**
     * Computes the exact y coordinate of this segment if it were extended
     * to the given x coordinate.  In other words, treats this segment as
     * an infinite line and calculates the y value at the given x. In the
     * case where this segment is vertical, an arbitrary y value is returned
     * if the given x lies on the line, or null otherwise.
     *
     * @param	x	the x coordinate 
     * @return	the y coordinate of this segment if extended to x, or null
     *		if the segment is vertical and does not coincide with x
     */
    public BigFraction yValue(BigFraction x) {
        if (isNotVertical()) {
	    // (x-X1)*(Y2-Y1)/(X2-X1)+Y1
	    return Y1.add(x.subtract(X1).multiply(dy()
			.divide(dx() )));
        } else {
            if (x.equals(X1)) {
                return Y1;
            } else {
                return null;
            }
        }
    }

    /**
     * Calculates the exact slope of the segment.
     * @return	the exact slope if not vertical, or {@code null} otherwise.
     */
    public BigFraction slope() {
        if (isNotVertical()) {
            return dy().divide(dx());
        } else {
            return null;
        }
    }

    @Override
    public boolean equals(Object b) {
        if (b == null || b.getClass() != this.getClass()) {
	    return false;
	}
	LineSegment seg = (LineSegment) b;
	return X1.equals(seg.X1) && X2.equals(seg.X2)
		    && Y1.equals(seg.Y1) && Y2.equals(seg.Y2)
		|| X2.equals(seg.X1) && X1.equals(seg.X2)
		    && Y2.equals(seg.Y1) && Y1.equals(seg.Y2);
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 79 * hash + (this.X1 != null ? this.X1.hashCode() : 0);
        hash = 79 * hash + (this.Y1 != null ? this.Y1.hashCode() : 0);
        hash = 79 * hash + (this.X2 != null ? this.X2.hashCode() : 0);
        hash = 79 * hash + (this.Y2 != null ? this.Y2.hashCode() : 0);
        return hash;
    }

    /**
     * Calculates determinant of the 2x2 matrix [ [dX1 dY1] [dX2 dY2] ]. 
     * The resulting value is useful in many ways: if 0, then the 2 segments
     * are parallel. If nonzero it can be used for calculating
     * intersections.  For the math behind it see this 
     * <a href="http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/">link</a>
     *
     * @param	l	a line segment
     * @return	the determinant of the 2x2 matrix [ [dX1 dY1] [dX2 dY2] ] 
     */
    private BigFraction determinant(LineSegment l) {
        BigFraction dX1 = dx();
        BigFraction dX2 = l.dx();
        BigFraction dY1 = dy();
        BigFraction dY2 = l.dy();

        // | dX1   dY1 |
        // |           | = dX1 * dY2 - dX2 * dY1
        // | dX2   dY2 |
        return dX1.multiply(dY2).subtract(dX2.multiply(dY1));
    }


    /**
     * Calculates determinant of the 2x2 matrix [ [dX1 dY1] [dX2 dY2] ]. 
     * The resulting value is useful in many ways: if 0, then the 2 segments
     * are parallel. If nonzero it can be used for calculating
     * intersections.  For the math behind it see this 
     * <a href="http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/">link</a>
     *
     * @param	dX2
     * @param	dY2
     * @return	the determinant of the 2x2 matrix [ [dX1 dY1] [dX2 dY2] ] 
     */
    private BigFraction determinant(BigFraction dX2, BigFraction dY2) {
        BigFraction dX1 = dx();
        BigFraction dY1 = dy();

        // | dX1   dY1 |
        // |           | = dX1 * dY2 - dX2 * dY1
        // | dX2   dY2 |
        return dX1.multiply(dY2).subtract(dX2.multiply(dY1));
    }

    /**
     * Tests if segments this and b are parallel. For the math behind
     * this see the comments for {@link #determinant(LineSegment)}.
     *
     * @param	b	a line segment
     * @return	true if this segment is parallel to b
     */
    public boolean isParallelTo(LineSegment b) {
        return determinant(b).equals(ZERO);
    }

    /**
     * Tests if segments this and b are collinear.
     *
     * @param	b	a line segment
     * @return	true if this segment is collinear to b
     */
    public boolean isCollinearTo(LineSegment b) {
        // first check parallel, then use segment P1-P3 to check collinear
        return this.isParallelTo(b) && this.isCollinearToParallelSegment(b);
    }

    /**
     * Tests if this segment is collinear to a parallel segment.
     *
     * @param	b	a parallel line segment
     * @return	true if a vertex of b is collinear with this segment
     */
    public boolean isCollinearToParallelSegment (LineSegment b) {
	return (X1.equals(b.X1) && Y1.equals(b.Y1)) || 
	    this.isParallelTo(new LineSegment(X1, Y1, b.X1, b.Y1));
    }

    /**
     * Tests if vertex is in the bounding box formed by this segment, 
     * inclusive of the edges.  "Bounding box" refers to the rectangle
     * with vertical and horizontal sides one of whose diagonals is this
     * segment.  Edge-inclusive means a point is considered "in" if it
     * lies on the edge of the rectangle.
     *
     * @param	point	a vertex to test
     * @return	true if point lies within or on the edge of the bounding box
     *		formed by this segment
     */
    public boolean boundingBoxContains(Vertex point) {
	// X1 <= X <= X2, Y1 <= Y <= Y2 OR X1 >= X >= X2, Y1 >= Y >= Y2
        if (point.getX().compareTo(min(X1, X2)) >= 0
		&& point.getX().compareTo(max(X1, X2)) <= 0
                && point.getY().compareTo(min(Y1, Y2)) >= 0
		&& point.getY().compareTo(max(Y1, Y2)) <= 0)
	{
            return true;
        } // else
        return false;
    }

    /**
     * Tests if input point lies on this segment, including endpoints.
     *
     * @param	a	a point
     * @return	true if this segment contains the given point
     */
    public boolean containsVertex(Vertex a){
        if(boundingBoxContains(a)
		&& (!isNotVertical() || a.getY().equals(yValue(a.getX())) ) )
	{ 
                return true;
        } // else
        return false;
    }

    /**
     * tests to see if the given vertex lies on the line corresponding
     * to the given line segment
     * @param  point	a vertex to test
     */
    public boolean onLine(Vertex point){	
        LineSegment c = new LineSegment(this.getVertex1(), point);
	return isParallelTo(c);
    }

    /**
     * Tests if the other line segment both is collinear to and
     * intersects this segment.
     *
     * @param	m	the other segment
     * @return	true if m is both collinear with and intersects this segment
     */
    public boolean collinearOverlaps(LineSegment m) {
	if (isCollinearTo(m)
		&& (boundingBoxContains(m.getVertex1())
		    || boundingBoxContains(m.getVertex2())
		    || m.boundingBoxContains(getVertex1())
		    || m.boundingBoxContains(getVertex2())) )
	{
            return true;
        }
        return false;
    }

    /**
     * Tests intersection for collinear segments only.
     *
     * @param	m	a collinear segment
     * @return	true if m intersects this segment
     */
    public boolean overlapsCollinearSegment(LineSegment m) {
	if ( (boundingBoxContains(m.getVertex1())
		    || boundingBoxContains(m.getVertex2())
		    || m.boundingBoxContains(getVertex1())
		    || m.boundingBoxContains(getVertex2())) )
	{
            return true;
        }
        return false;
    }

    /**
     * Tests if this segment is collinear to and intersects segment b.
     * Functionally equivalent to {@link #collinearOverlaps(LineSegment)},
     * but different implementation.
     *
     * @param	b	the other segment
     * @return	true if b is both collinear with and intersects this segment
     */
    public boolean overlaps(LineSegment b) {
        if (isParallelTo(b) && intersects(b)) {
            return true;
        }
        return false;
    }

    /**
     * Takes in a segment that overlaps this and returns the union of this
     * and the other segment. In other words, merges the two segments into
     * one segment that covers both.
     * REQ: b overlaps this segment
     *
     * @param	b	a segment that overlaps this segment
     * @return	a new segment that is the union of this and b
     */
    public LineSegment mergeOverlapping (LineSegment b) {
	List<Vertex> vertices = new ArrayList<Vertex>();
	return new LineSegment();
    }

    /**
     * Private utility function that treats both segments as parametric
     * lines and solves for the paramters s and t where they intersect.
     * The exact precision results are returned as the coordinates of a
     * Vertex. This is a bit of a kludge, but it works.
     * For the math see comment to {@link #determinant(LineSegment)}.
     * REQ: b must NOT be parallel to this segment
     *
     * @param	b	the other segment
     * @return	a Vertex whose x corresponds to the s parameter for this
     *		segment and whose y corresponds to the t parameter for b
     */
    private Vertex solveParametricIntersections (LineSegment b) {
        //LineSegment c = new LineSegment(this.getVertex1(), b.getVertex1());
	BigFraction cdX = b.X1.subtract(X1);
	BigFraction cdY = b.Y1.subtract(Y1);

        BigFraction denom = this.determinant(b);
        BigFraction num_sa = b.determinant(cdX, cdY).negate();
        BigFraction num_tb = determinant(cdX, cdY).negate();

        BigFraction sa = num_sa.divide(denom);
        BigFraction tb = num_tb.divide(denom);
	return new Vertex(sa, tb);
    }

    /**
     * Private utility function that treats this segment as a parametric
     * line with t=0 being (X1,Y1) and t=1 being (X2,Y2) and computes the 
     * point corresponding to the given parameter t
     * REQ: b must NOT be parallel to this segment
     *
     * @return	the point along the line at the parameter t
     */
    private Vertex pointAtParameter(BigFraction t) {
        // x = (1-t)*X1+t*X2 = X1 + t(X2-X1)
        BigFraction x = this.X1.add(t.multiply(dx()));

        // y = (1-t)*Y1+t*Y2 = Y1 + t(Y2-Y1)
        BigFraction y = this.Y1.add(t.multiply(dy()));

        Set<LineSegment> visibility = new HashSet<LineSegment>();
        visibility.add(this);

        return new Vertex(visibility, x, y);
    }

    /**
     * Calculates intersection point of 2 line segments. For the math
     * see comments for {@link #determinant(LineSegment)}.
     * REQ: b must NOT be parallel to this segment
     *
     * @param   b	the other segment
     * @return  the intersection of the two segments if it exists with
     *		visibility, or {@code null} otherwise.
     */
    public Vertex intersectionPoint(LineSegment b) {
	Vertex parameters = solveParametricIntersections(b);

        BigFraction sa = parameters.getX();
        BigFraction tb = parameters.getY();

        // in range if 0 <= BOTH sa, tb <= 1
        // -.5 <= sa, tb - .5 <= .5
        // |sa,tx - .5| <= .5
        // out of range if |EITHER sa,tx - .5| > .5
        if (sa.subtract(ONE_HALF).abs().compareTo(ONE_HALF) > 0 ||
	    tb.subtract(ONE_HALF).abs().compareTo(ONE_HALF) > 0     )
	{
            return null;
        } // else, intersection exists

	Vertex intersection = pointAtParameter(sa);
	intersection.mergeVisibility(singleton(b));
	return intersection;
    }

    /**
     * Calculates the coordinates where the lines corresponding to
     * segments this and b intersect.
     * For the math see comment to {@link #determinant(LineSegment)}.
     * REQ: b must NOT be parallel to this segment
     *
     * @param	b	the segment to intersect
     * @return	the intersection or null if the segments are parallel
     */
    public Vertex lineIntersection (LineSegment b) {
	Vertex parameters = solveParametricIntersections(b);

        BigFraction sa = parameters.getX();
	Vertex intersection = pointAtParameter(sa);
	intersection.mergeVisibility(singleton(b));
	return intersection;
    }

    /*
    public Vertex intersection(LineSegment b) {
        BigFraction x = new BigFraction(0);
        BigFraction y = new BigFraction(0);

        BigFraction x1 = X1;
        BigFraction y1 = Y1;
        BigFraction x2 = X2;
        BigFraction y2 = Y2;
        BigFraction x3 = b.getX1();
        BigFraction y3 = b.getY1();
        BigFraction x4 = b.getX2();
        BigFraction y4 = b.getY2();


        Vector<String> segs = new Vector<String>();
        segs.add(lName);
        segs.add(b.getName());


        if (x1.equals(x2)) {
            if (x3.equals(x4)) {
                if (x3.equals(x2)) {
                    if (yValue(x3).equals(y1)) {
                        return new Vertex(segs, x3, y1);
                    } else if (yValue(x3).equals(y2)) {
                        return new Vertex(segs, x3, y2);
                    } else if (yValue(x4).equals(y1)) {
                        return new Vertex(segs, x4, y1);
                    } else if (yValue(x4).equals(y2)) {
                        return new Vertex(segs, x4, y2);
                    } else {
                        if (y4.compareTo(y3) >= 0) {
                            return new Vertex(segs, x1, y3);
                        } else {
                            return new Vertex(segs, x4, y4);
                        }
                    }
                } else {
                    return null;
                }
            }
            x = x1;
            BigFraction s2 = (y4.subtract(y3)).divide(x4.subtract(x3));
            y = s2.multiply(x.subtract(x3)).add(y3);
        } else if (x3.equals(x4)) {
            x = x3;
            BigFraction s1 = (y2.subtract(y1)).divide(x2.subtract(x1));
            y = s1.multiply(x.subtract(x1)).add(y1);
        } else {
            BigFraction s1 = (y2.subtract(y1)).divide(x2.subtract(x1));
            BigFraction s2 = (y4.subtract(y3)).divide(x4.subtract(x3));
            //x = (x1*(x4*(y3-y2)+x3*(y2-y4))+x2*(x4*(y1-y3)+x3*(y4-y1)))/(-(x3-x4)*(y1-y2)+(x1-x2)*(y3-y4));
            x = (x1.multiply(x4.multiply(y3.subtract(y2)).add(x3.multiply(y2.subtract(y4)))).add(x2.multiply(x4.multiply(y1.subtract(y3)).add(x3.multiply(y4.subtract(y1)))))).divide(((x4.subtract(x3)).multiply(y1.subtract(y2)).add((x1.subtract(x2)).multiply(y3.subtract(y4)))));
            //y = s1*(x-x1)+y1;
            y = s1.multiply(x.subtract(x1)).add(y1);

        }

        return new Vertex(segs, x, y);
    }*/

    /**
     * Tests if this segment intersects b.
     *
     * @param	b	the segment to test intersection
     * @return	true if an intersection exists, false otherwise
     */
    public boolean intersects(LineSegment b) {
	if (this.isParallelTo(b)) {
	    if (this.isCollinearToParallelSegment(b)) {
		return overlapsCollinearSegment(b);
	    } // else
	    return false;
	} // else
	return intersectionPoint(b) != null;
    }

    /**
     * Extends the line segment to some integer endpoint within the given
     * window [xmin,xmax],[ymin,ymax].  It is required that the segment is
     * properly contained in this window.
     *
     * @param	endpoint    1 or 2, specifies which endpoint to extend
     * @param	xmin	    x coordinate of lower left corner of the window
     * @param	ymin	    y coordinate of lower left corner of the window
     * @param	xmax	    x coordinate of upper right corner of the window
     * @param	ymax	    y coordinate of upper right corner of the window
     * @return	a new extended LineSegment
     */
    public LineSegment extend(
	    int endpoint, int xmin, int ymin, int xmax, int ymax)
    {
        LineSegment bottom = new LineSegment(new BigFraction(xmin), new BigFraction(ymin),
                new BigFraction(xmax), new BigFraction(ymin));
        LineSegment left = new LineSegment(new BigFraction(xmin), new BigFraction(ymin),
                new BigFraction(xmin), new BigFraction(ymax));
        LineSegment right = new LineSegment(new BigFraction(xmax), new BigFraction(ymin),
                new BigFraction(xmax), new BigFraction(ymax));
        LineSegment top = new LineSegment(new BigFraction(xmin), new BigFraction(ymax),
                new BigFraction(xmax), new BigFraction(ymax));

        Vertex bvert;
        Vertex tvert;
        Vertex lvert;
        Vertex rvert;

        if(isParallelTo(bottom)){
            bvert = null;
            tvert = null;
        }else{
            bvert = lineIntersection(bottom);
            tvert = lineIntersection(top);
        }

        if(isParallelTo(left)){
            lvert = null;
            rvert = null;
        }
        else{
            lvert = lineIntersection(left);
            rvert = lineIntersection(right);
        }
        
       

        Vector<Vertex> validvert = new Vector<Vertex>();

        BigFraction Xmin = new BigFraction(xmin);
        BigFraction Xmax = new BigFraction(xmax);
        BigFraction Ymin = new BigFraction(ymin);
        BigFraction Ymax = new BigFraction(ymax);


        if(bvert!=null){
            if(bvert.getX().compareTo(Xmin)>=0 && bvert.getX().compareTo(Xmax)<=0 &&
                    bvert.getY().compareTo(Ymin)>=0 && bvert.getY().compareTo(Ymax)<=0)
                validvert.add(bvert);
        }
        if(lvert!=null){
            if(lvert.getX().compareTo(Xmin)>=0 && lvert.getX().compareTo(Xmax)<=0 &&
                    lvert.getY().compareTo(Ymin)>=0 && lvert.getY().compareTo(Ymax)<=0)
                validvert.add(lvert);
        }
        if(rvert!=null){
            if(rvert.getX().compareTo(Xmin)>=0 && rvert.getX().compareTo(Xmax)<=0 &&
                    rvert.getY().compareTo(Ymin)>=0 && rvert.getY().compareTo(Ymax)<=0)
                validvert.add(rvert);
        }
        if(tvert!=null){
            if(tvert.getX().compareTo(Xmin)>=0 && tvert.getX().compareTo(Xmax)<=0 &&
                    tvert.getY().compareTo(Ymin)>=0 && tvert.getY().compareTo(Ymax)<=0)
                validvert.add(tvert);
        }

        Vertex endpt = new Vertex();
        Vertex endpt2 = new Vertex();
        if (endpoint == 1) {
            endpt.setX(X1);
            endpt.setY(Y1);
            endpt2.setX(X2);
            endpt2.setY(Y2);
        } else if (endpoint == 2) {
            endpt.setX(X2);
            endpt.setY(Y2);
            endpt2.setX(X1);
            endpt2.setY(Y1);
        }

        Vertex critical = validvert.firstElement();
        Vertex c2 = validvert.lastElement();

        if (critical.distanceTo(endpt) > critical.distanceTo(endpt2)) {
            critical = c2;
        }

        LineSegment newEndPtSpace = new LineSegment(endpt, critical);

        double xbegin = 0;
        double xend = 0;
        double ybegin = 0;
        double yend = 0;

        BigFraction randx = new BigFraction(0);
        BigFraction randy = new BigFraction(0);

        if (isNotVertical()) {
            if (endpt.getX().compareTo(critical.getX()) == -1) {
                xbegin = endpt.getX().doubleValue();
                xend = critical.getX().doubleValue();
            } else {
                xend = endpt.getX().doubleValue();
                xbegin = critical.getX().doubleValue();
            }

            double rand = (Math.random() * (xend - xbegin) + xbegin);
            int randi = (int) (rand * 1000);
            randx = new BigFraction(randi, 1000);
            randy = yValue(randx);
        } else {
            randx = X1;
            if (endpt.getY().compareTo(critical.getY()) == -1) {
                ybegin = endpt.getY().doubleValue();
                yend = critical.getY().doubleValue();
            } else {
                yend = endpt.getY().doubleValue();
                ybegin = critical.getY().doubleValue();
            }
            double rand = (Math.random() * (yend - ybegin) + ybegin);
            int randi = (int) (rand * 1000);
            randy = new BigFraction(randi, 1000);
        }

        LineSegment rsegment = new LineSegment();
        if (endpoint == 1) {
            rsegment = new LineSegment(randx, randy, X2, Y2);
        } else if (endpoint == 2) {
            rsegment = new LineSegment(X1, Y1, randx, randy);
        }

        return rsegment;
    }

    /**
     * Returns a {@link Comparator} that compares segments by angle
     * on the unit circle, where the angles are in the interval
     * [0,2pi) radians.
     *
     * @return	a Comparator that compares segments by arctan
     */
    public static Comparator<LineSegment> getRadianComparator() {
	return _radianComparator;
    }

    private static class RadianComparator
	    implements Comparator<LineSegment> 
    {
	public int compare (LineSegment l, LineSegment m) {
	    if (l.equals(m)) { return 0; }
	    int ql = quadrant(l);
	    int qm = quadrant(m);
	    if (ql != qm ) { return Integer.valueOf(ql).compareTo(qm); }
	    else { // if (ql == qm) { // same quadrant
		switch (ql) {
		    case 1: return quadrant1Compare(l, m);
		    case 2: return quadrant2Compare(l, m);
		    case 3: return quadrant3Compare(l, m);
		    case 4: return quadrant4Compare(l, m);
		    // default should never be reached
		    default: throw new
			    RuntimeException("Illegal Quadrant: " + ql);
		}
	    }
	}

	/**
	 * Computes the quadrant that contains the segment, using
	 * Vertex1 as the origin. 
	 * Quadrant   I includes the positive x axis.
	 * Quadrant  II includes the positive y axis.
	 * Quadrant III includes the negative x axis.
	 * Quadrant  IV includes the negative y axis.
	 *
	 *  Y\X |    -    0    +
	 *  ----+----------------
	 *   -  |  III   IV   IV
	 *   0  |  III  n/a    I
	 *   +  |   II   II    I
	 */
	private int quadrant (LineSegment l) {
	    int x = l.dx().compareTo(ZERO);
	    int y = l.dy().compareTo(ZERO);
	    if (x > 0) {
		if (y < 0)  return 4;
		else	    return 1;
	    } else if (x==0) {
		if (y < 0)  return 4;
		else	    return 2;
	    } else { // if (x < 0) {
		if (y > 0)  return 2;
		else	    return 3;
	    }
	}
	
	/**
	 * Compares two segments in quadrant 1 with Vertex1 == (0,0)
	 *
	 * @param   l	    a segment in quadrant I
	 * @param   m	    a segment in quadrant I
	 * @return  same as compareTo and compare
	 */
	private int quadrant1CompareVectors(LineSegment l, LineSegment m) {
	    return l.yValue(ONE).compareTo(m.yValue(ONE));
	}

	/**
	 * Compares two segments in quadrant I. Simply compares their
	 * y coordinates at x=1, since quadrant I does not contain vertical
	 * segments.
	 *
	 * @param   l	    a segment in quadrant I
	 * @param   m	    a segment in quadrant I
	 * @return  same as compareTo and compare
	 */
	private int quadrant1Compare(LineSegment l, LineSegment m) {
	    LineSegment ol = new LineSegment(ZERO, ZERO, l.dx(), l.dy());
	    LineSegment om = new LineSegment(ZERO, ZERO, m.dx(), m.dy());
	    return quadrant1CompareVectors(ol, om);
	}

	/**
	 * Compares two segments in quadrant II. Rotates the segments 
	 * 90 degrees clockwise and uses quadrant I case.
	 *
	 * @param   l	    a segment in quadrant II
	 * @param   m	    a segment in quadrant II
	 * @return  same as compareTo and compare
	 */
	private int quadrant2Compare(LineSegment l, LineSegment m) {
	    LineSegment ol =
		new LineSegment(ZERO, ZERO, l.dy(), l.dx().negate() );
	    LineSegment om =
		new LineSegment(ZERO, ZERO, m.dy(), m.dx().negate() );
	    return quadrant1CompareVectors(ol, om);
	}
	
	/**
	 * Compares two segments in quadrant III. Rotates 180 degrees and
	 * treats as quadrant I.
	 *
	 * @param   l	    a segment in quadrant III
	 * @param   m	    a segment in quadrant III
	 * @return  same as compareTo and compare
	 */
	private int quadrant3Compare(LineSegment l, LineSegment m) {
	    LineSegment ol = new LineSegment(
		    ZERO, ZERO, l.dx().negate(), l.dy().negate());
	    LineSegment om = new LineSegment(
		    ZERO, ZERO, m.dx().negate(), m.dy().negate());
	    return quadrant1CompareVectors(ol, om);
	}
	
	/**
	 * Compares two segments in quadrant IV. Rotates segments 90 
	 * degrees counter clockwise (270 degrees clockwise) and uses
	 * quadrant I case.
	 *
	 * @param   l	    a segment in quadrant IV
	 * @param   m	    a segment in quadrant IV
	 * @return  same as compareTo and compare
	 */
	private int quadrant4Compare(LineSegment l, LineSegment m) {
	    LineSegment ol =
		new LineSegment(ZERO, ZERO, l.dy().negate(), l.dx());
	    LineSegment om =
		new LineSegment(ZERO, ZERO, m.dy().negate(), m.dx());
	    return quadrant1CompareVectors(ol, om);
	}
	
    }
}

